In recent years, since multimedia-related technology has been developed and large-capacity recording media have become available, a system has been getting popular in which digital contents (hereafter, simply referred to as “contents”) that are made of video, audio, and the like are generated and distributed as being stored in a large capacity recording medium such as an optical disc or distributed via a network or by broadcast.
Distributed contents are read with the use of a computer, a playback apparatus, or the like, so that they can be played back or duplicated.
Generally speaking, an encryption technique is used in order to protect copyrights of contents, in other words, in order to prevent illegitimate use of contents such as illegitimate playback and illegitimate duplication.
More specifically, contents are encrypted with the use of an encryption key and distributed as being recorded on a recording medium such as an optical disc. With regards to such contents, only terminal apparatuses that each have a decryption key corresponding to the encryption key are able to decrypt data read from the recording medium, using the decryption key and to, for example, play back the contents. It should be noted that, when contents are encrypted and recorded onto a recording medium, different methods are used such as (i) contents are encrypted with an encryption key corresponding to a decryption key stored in a terminal apparatus and then recorded and (ii) contents are encrypted with a key and recorded, and then a decryption key that corresponds to the key is encrypted with an encryption key that corresponds to the decryption key stored in a terminal apparatus and recorded.
In such cases, it is necessary to strictly manage the decryption key stored in the terminal apparatus so that it is not disclosed to the outside. There is a risk, however, that such a key may be disclosed to the outside when an illegitimate user analyzes the inside of the terminal apparatus. Once an illegitimate user has discovered such a key, there are chances that the illegitimate user may manufacture a recording apparatus, a playback apparatus, or software for illegitimately utilizing the contents and distribute it via the Internet and the like. In such situations, the copyright holder would want to make sure that the once-disclosed key becomes unable to handle the contents to be provided in the future. A technique to realize this is called a key revocation technique. The Patent Document 1 and the Non-Patent Document 1 disclose systems that realize key revocation with the use of a hierarchical structure called a tree structure.
The following describes a conventional key revocation technique disclosed in the Non-Patent Document 1.
Firstly, a “subset difference” is to be defined. A subset difference is defined as a set being made up of apparatuses (leaves) obtained by excluding a set of a smaller tree structure from a set of a larger tree structure. The subset difference is determined by specifying two roots, namely one root for the larger tree structure and the other root for the smaller tree structure. A decryption key is assigned to each subset difference.
Further, a content is encrypted with a content key, and each apparatus owns a decryption key. A piece of data that required for each apparatus to obtain a content key using the decryption key stored in the apparatus will be referred to as key data. Generally speaking, a piece of key data is distributed along with a content. In the case where a recording medium is used for distribution of a content, a piece of key data is recorded on the recording medium.
It is possible to reduce the size of a piece of key data by supplementing a set of unrevoked apparatuses with a subset difference. FIG. 42 is a diagram that shows the concept. In FIG. 42, the root of the larger tree structure T1000 is Vi, and the root of the smaller tree structure T1001 is Vj. A set for revoking apparatuses assigned to the two leaves marked with the Xs is a subset difference 1001 “Si, j” obtained by excluding the tree structure T1001 from the tree structure T1000. The required key data is an encrypted content key that is encrypted using an encryption key “Li, j” corresponding to the subset difference “Si, j”. To be more specific, the subset difference is a set of leaves belonging to a remainder portion obtained by excluding a conceptual drawing T1003 conceptually representing the tree structure T1001 from a conceptual drawing T1002 conceptually representing the tree structure T1000.
As another example, FIG. 43 shows a subset difference and an encryption key “Si, j” to be used for encrypting a content key in the case where the apparatuses 3, 4, 13, and 15 are revoked in a tree structure with sixteen apparatuses. For example, the apparatuses 9 to 12 belong to a subset difference 2001 “S3, 7” obtained by excluding the tree structure T2001 whose root is V7 from the tree structure T2000 whose root is V3. In FIG. 43, apparatuses that belong to a subset difference “Si, j” each own a decryption key in common. For example, the apparatuses 1, 2, and 5 to 8 that belong to the subset difference 2002 “S2, 9” each own a decryption key “L2, 9” in common. The apparatuses 9 to 12 that belong to the subset difference 2001 “S3, 7′” each own a decryption key “L3, 7” in common. Further, since a content key is encrypted with each of “L2, 9”, “L3, 7”, “L14, 28”, and “L15, 31”, the apparatuses 3, 4, 13, and 15 having none of the decryption keys are unable to decrypt the content key and are unable to deal with the contents.
Here, each of the apparatuses needs to own a decryption key in correspondence with the positional relationship of the revoked apparatuses. The concept in principle can be explained as follows: If an apparatus owns a decryption key “Li, j” in correspondence with a subset difference “Si, j”, then the apparatus also owns a decryption key “Li, k” in correspondence with a subset difference “Si, k”, where Vk is a subset of Vj. In such a case, a one-way function is used in order to have an arrangement wherein it is possible to calculate “Li, k” from “Li, j”, but it is impossible to calculate “Li, j” from “Li, k”.
First of all, explanation is provided on encryption keys (that are in correspondence with decryption keys owned by apparatuses) assigned to the nodes in a tree structure, with reference to the example of a tree structure T3000 having binary trees shown in FIG. 44. It should be noted that FIG. 44 shows a part of the tree structure T3000 which manages eight apparatuses in total.
Mutually distinctive T-bit identifiers called “labels” are respectively provided for the nodes in the tree structure T3000 shown in FIG. 44. A pseudo random number generator G is provided that is operable to generate a 3T-bit random number in response to an inputted data length of T bits. In the case where a label “A1” is inputted to the pseudo random number generator G, among the 3T bits to be outputted, the first T bits are taken as a label of a child positioned on the bottom left of the label 3001 “A1”, and the middle T bits are taken as an encryption key in correspondence with the node having the label 3001 “A1”, while the last T bits are taken as a label of a child positioned on the bottom right of the label 3001 “A1”. These three pieces of T-bit data are expressed as “A1L”, “A1M”, and “A1R”, respectively. In FIG. 44, the labels “A1”, “A2”, “A3”, and “A4” . . . are assigned to the nodes respectively in advance. In addition, a new label that derives from an upper label is added. For example, three labels are assigned to the node 4001 on the third layer from the top. More specifically, the three labels are the label “A4” assigned to this node in advance, as well as a label “A1LL” which derives from the upper label “A1” and a label “A2L” which also derives from an upper label “A2”. Further, the number of encryption keys assigned to a node is equal to the number of the labels assigned to the node. For example, three encryption keys, namely, “A1LLM”, “A2LM”, and “A4M” are assigned to the node 4001.
Here, the following describes the relationship between an encryption key “Li, j” in correspondence with a subset difference “Si, j” and encryption keys assigned to the nodes. When a node Vi and a node Vj are given, the encryption key “Li, j” in correspondence with the subset difference “Si, j” is an encryption key in correspondence with a label added to the node Vj, among the labels deriving from a label assigned to the node Vi. In the example shown in FIG. 44, if the label of the node Vi is A1, and the label of the Vj is A4, the encryption key “Li, j” is “A1LLM”.
Next, explanation is provided on decryption keys to be assigned to the apparatuses. Here, a plurality of labels assigned to a node are assigned to an apparatus. Each apparatus generates, within the apparatus itself, a decryption key from corresponding labels, using the pseudo random number generator G. Further, explanation is provided on an example of secret key encryption in which an encryption key is identical to a decryption key.
Specifically, the attention is focused on a node being subordinate to a node positioned on a path between a leaf to which an apparatus is assigned and the root so that the labels that are assigned to the node and derive from another node positioned above the node are to be assigned to the apparatus.
For example, the labels to be assigned to the apparatus 1 shown in FIG. 44 are six labels, namely, “A1LLR”, “A2LR”, “A4R”, “A1LR”, “A2R”, and “A1R”. It should be noted that since the labels “A3”, “A5”, and “A7” are assigned to corresponding nodes respectively in advance, these labels are not assigned to the apparatus 1.
The total number of the labels to be assigned to each apparatus can be expressed as 0.5(log2 t)^2+0.5 log2 t, where the total number of the apparatuses is t. The calculation is based on the following: the number of the labels to be assigned to an apparatus is one from the second layer, two from the third layer, . . . and log2 t from the lowermost layer. Consequently, the total number of the labels is 1+2+ . . . +log2 t=0.5(log2 t)^+0.5 log2 t. For example, in the case where the total number of the apparatuses is eight, the number of the labels to be assigned to each apparatus is six.
The following describes an example in which some apparatuses are actually revoked, with reference to FIG. 44.
In an initial state where none of the apparatuses are revoked, a content key is encrypted using the keys “A1LM” and “A1RM” that are in correspondence with the label 3002 “A1L” and the label 3003 “A2R”. Each of all the apparatuses owns either the label 3002 “A1L” or the label 3003 “A1R”, and is able to generate a decryption key either “A1LM” or “A1RM” from the owned label. Accordingly, each apparatus is able to decrypt a content key with the generated decryption key and is further able to decrypt a content using the decrypted content key.
In the case where the apparatus 1 is hacked and all the keys owned by the apparatus 1 have been disclosed, the label 3001 “A1” and the label 3004 “A1LLL” are specified, and the smaller tree structure (leaf) T3001 having the label 3004 “A1LLL” is taken out from the larger tree structure T3000 whose root is the label 3001 “A1”. The content key is encrypted using the encryption key “A1LLLM” which is in correspondence with the label 3004 “A1LLL”. With this arrangement, since the pseudo random generator G is a one-way function, the apparatus 1 is not able to generate a decryption key “ALLLM” from any label stored within the apparatus 1, and is therefore not able to decrypt the content key. Each of apparatuses other than the apparatus 1 either stores therein the label 3004 “A1LLL” or is able to generate the label 3004 “A1LLL” from a label stored in the apparatus, using a pseudo random generator. In other words, each of apparatuses other than the apparatus 1 is able to generate a decryption key “A1LLLM” For example, the apparatus 2 stores therein the label 3004 “A1LLL” and is therefore able to generate the decryption key “A1LLLM” from the stored label 3004 “A1LLL”. Each of the two leaves (not shown in the drawing; for example the apparatuses 3 and 4) being subordinate to the node that is in correspondence with the label 3006 “A5” stores therein the label 3005 “A1LL”. In other words, each of the apparatuses 3 and 4 is able to generate the decryption key “A1LLLM” from the stored label 3005 “A1LL”. Each of the leaves i.e. the grandchild nodes (not shown in the drawing; for example, the apparatuses 5, 6, 7, and 8) being subordinate to the node that is in correspondence with the label “A3” stores therein the label 3002 “A1L”. In other words, each of the apparatuses 5 to 8 is able to generate the decryption key “A1LLLM” from the stored label 3002 “A1L”.
As explained above, the system disclosed in the Non-Patent Document 1 realizes key revocation.
Patent Document 1: The Japanese Unexamined Patent Application Publication No. 2002-281013
Non-Patent Document 1: D. Naor, M. Naor, and J. Lotspiech, “Revocation and Tracing schemes for Stateless Receivers”, Proceedings of CRYPTO 2001, LNCS2139, pp. 41-62, 2001.